/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef int TElemType;

/* 用于构造二叉树********************************** */
// int idx=1;
// typedef int Arr[200]; /*  0号单元存放串的长度 */
// Arr arr;


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return liftIsRight(root->left, root->right);
    }
    bool liftIsRight(TreeNode* left, TreeNode* right) {
        if(!left && !right) return true;  // 都为空
        if(!left || !right) return false; // 其中一个为空

        if (left->val == right->val)
        {
            return liftIsRight(left->left, right->right) && liftIsRight(left->right, right->left);;
        }
        return false;

    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(3);

    cout << solu.isSymmetric(root) << endl;

    return 0;
}